# coding: utf8
# datetime: 2021-04-10
# 题目地址: https://leetcode-cn.com/problems/ugly-number/


from typing import List


class Solution:
    def isUgly(self, n: int) -> bool:
        if n < 0:
            return False
        for factor in [2,3,5]:
            while n%factor == 0:
                n /= factor
        return n == 1

a = Solution()
print(a.isUgly(10))


# recursion 解法
# def isUgly(n: int, factor: int, resp: List[int]) -> None:
#     tmp = n/factor
#     # print(tmp)
#     if tmp < 1:
#         return
#     if tmp == 1:
#         print(resp)
#         return
    
#     for factor_ in [2,3,5]:
#         resp.append(factor_)
#         isUgly(tmp, factor_, resp)
#         resp.pop()

# isUgly(100, 1, [])